package com.lishem.leftgod.level1.class04;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * 有一个源源不断地吐出整数的数据流，假设你有足够的空间来保存吐出的数。
 * 请设计一个名叫MedianHolder的结构，MedianHolder可以随时取得之前吐出所有数的中位数。
 * 1．如果MedianHolder已经保存了吐出的N个数，那么任意时刻
 * 将一个新数加入到MedianHolder的过程，其时间复杂度是O(logN)。
 * 2．取得已经吐出的N个数整体的中位数的过程，时间复杂度为O(1)。
 * 如果个数是偶数，返回均值
 */
public class Code_01_MadianQuick {

    public static class MedianHolder {
        private PriorityQueue<Integer> maxHeap = new PriorityQueue<>((num1, num2) -> {
            return num2 - num1;
        });
        private PriorityQueue<Integer> minHeap = new PriorityQueue<>((num1, num2) -> {
            return num1 - num2;
        });


        public void addNumber(int num) {
            if (!maxHeap.isEmpty() && maxHeap.peek() > num) {
                maxHeap.add(num);
            } else {
                minHeap.add(num);
            }
            if (maxHeap.size() - minHeap.size() == 2) {
                minHeap.add(maxHeap.poll());
            } else if (minHeap.size() - maxHeap.size() == 2) {
                maxHeap.add(minHeap.poll());
            }
        }

        public Integer getMedian() {
            int size = maxHeap.size() + minHeap.size();
            if (size == 0) {
                return null;
            }
            if (size == 1) {
                return maxHeap.isEmpty() ? minHeap.peek() : maxHeap.peek();
            }
            if ((size & 1) == 0) {
                return (maxHeap.peek() + minHeap.peek()) / 2;
            } else {
                return maxHeap.size() > minHeap.size() ? maxHeap.peek() : minHeap.peek();
            }
        }
    }

    public static int getMedianOfArray(int[] arr) {
        int[] newArr = Arrays.copyOf(arr, arr.length);
        Arrays.sort(newArr);
        int mid = (newArr.length - 1) / 2;
        if ((newArr.length & 1) == 0) {
            return (newArr[mid] + newArr[mid + 1]) / 2;
        } else {
            return newArr[mid];
        }
    }

    public static void printArray(int[] arr) {
        for (int i = 0; i != arr.length; i++) {
            System.out.print(arr[i] + ",");
        }
        System.out.println();
    }


    // for test
    public static int[] getRandomArray(int maxLen, int maxValue) {
        int[] res = new int[(int) (Math.random() * maxLen) + 1];
        for (int i = 0; i != res.length; i++) {
            res[i] = (int) (Math.random() * maxValue);
        }
        return res;
    }

    public static void main(String[] args) {
        boolean err = false;
        int testTimes = 200000;
        for (int i = 0; i != testTimes; i++) {
            int len = 30;
            int maxValue = 1000;
            int[] arr = getRandomArray(len, maxValue);
            arr = new int[]{310, 449, 654, 788, 840, 866};
            MedianHolder medianHold = new MedianHolder();
            for (int j = 0; j != arr.length; j++) {
                medianHold.addNumber(arr[j]);
            }
            if (medianHold.getMedian() != getMedianOfArray(arr)) {
                err = true;
                printArray(arr);
                break;
            }
        }
        System.out.println(err ? "Oops..what a fuck!" : "today is a beautiful day^_^");

    }

}
